package algorithm.search.insertValue;

import java.util.*;

public class InsertValue {
    public static void main(String[] args) {
        int[] arr = {-12, -4, -3, 5, 9, 40, 60};
        System.out.println(insertValue(arr, 0, arr.length - 1, -4));
    }

    /**
     * 插值查找
     * 自适应算法
     *
     * @param arr
     * @param left
     * @param right
     * @param val
     * @return
     */
    public static int insertValue(int[] arr, int left, int right, int val) {
        //在这里比二分多了两个退出条件，防止mid越界
        if (right < left || val < arr[0] || val > arr[arr.length - 1])
            return -1;
        //这里和二分求mid不一样，自适应
        int mid = left + (right - left) * ((val - arr[left]) / (arr[right] - arr[left]));
        if (val == arr[mid])
            return mid;
        if (val > arr[mid]) {
            return insertValue(arr, mid + 1, right, val);
        } else {
            return insertValue(arr, left, mid - 1, val);
        }

    }
}
